home *** CD-ROM | disk | FTP | other *** search
/ Aminet 5 / Aminet 5 - March 1995.iso / Aminet / dev / misc / LEDA_gene.lha / LEDA-3.1c-generic / incl / LEDA / tree_collection.h < prev    next >
Encoding:
C/C++ Source or Header  |  1994-08-05  |  4.1 KB  |  135 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  3.1c
  4. +
  5. +
  6. +  tree_collection.h
  7. +
  8. +
  9. +  Copyright (c) 1994  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16. #ifndef LEDA_DYNTREES_H
  17. #define LEDA_DYNTREES_H
  18.  
  19. #include <LEDA/basic.h>
  20.  
  21.  /*********************************************************************
  22.  *                                                                     *
  23.  *  dyna_trees T; deklariert eine (vorerst leere) Menge von dyn_trees  *
  24.  *                                                                     *
  25.  *  d_vertex T.maketree(); Erzeugt einen Baum, der genau einen Knoten  *
  26.  *     enthaelt (der in keinen anderem Baum enthalten ist.             *
  27.  *                                                                     *
  28.  *  d_vertex T.findroot(d_vertex v); Gibt die Wurzel des v enthaltenden*
  29.  *     Baumes zurueck.                                                 *
  30.  *                                                                     *  
  31.  *  d_vertex T.findcost(d_vertex v, double& d); Gibt den entsprechenden*
  32.  *     Knoten zurueck (s.o.), die Kosten werden im Argument d zurueck- *
  33.  *     gegeben.                                                        *
  34.  *                                                                     *
  35.  *  void   T.addcost(d_vertex v, double x); s.o.                       *
  36.  *                                                                     *
  37.  *  void   T.link(d_vertex v, d_vertex w); s.o.                        *
  38.  *                                                                     *
  39.  *  void   T.cut(d_vertex v); s.o.                                     *
  40.  *                                                                     *
  41.  *                                                                     *
  42.  * Implemented by Jan Timm                                             *
  43.  *                                                                     *
  44.  *********************************************************************/
  45.  
  46.  
  47.  
  48.  
  49.  
  50. class d_node;
  51. typedef d_node *d_vertex;
  52. typedef d_node *d_path;
  53.  
  54. class d_node {
  55.  
  56. friend class dyna_trees;
  57.  
  58.      void*    info;        // user-defined information
  59.  
  60.      d_vertex left,        // linkes Kind
  61.               right,       // rechtes Kind
  62.               parent,      // Elter
  63.               successor,   // Nachfolger (fuer Pfad)
  64.               next;        // fuer Verkettung fuer ~dyna_tree
  65.  
  66.      double dcost,
  67.             dmin;
  68.  
  69.      d_node(void* i) { 
  70.                        left=right=parent=successor=next=0;
  71.                        dcost=dmin=0;
  72.                        info = i;
  73.                       };
  74.    LEDA_MEMORY(d_node)
  75.  
  76. };
  77.   
  78.    
  79. class dyna_trees {
  80.      d_vertex first,
  81.             last;  // diese beiden Zeiger fuer ~dyna_tree
  82.  
  83.      void splay(d_vertex);
  84.  
  85.      d_vertex assemble(d_vertex, d_vertex, d_vertex);
  86.      void   disassemble(d_vertex, d_vertex&, d_vertex&);
  87.  
  88.      d_vertex makepath(void*);
  89.      d_vertex findpath(d_vertex);
  90.      d_vertex findpathcost(d_path, double&);
  91.      d_vertex findtail(d_path);
  92.      void   addpathcost(d_path, double);
  93.      d_vertex join(d_path, d_path, d_path);
  94.      void   split(d_vertex, d_vertex&, d_vertex&);
  95.      
  96.      d_path   expose(d_vertex);
  97.  
  98. virtual void copy_inf(GenPtr& x)      { x=x; }
  99. virtual void clear_inf(GenPtr& x)     { x=0; }
  100.  
  101. public:
  102.      dyna_trees() { first=last=0; };
  103.      virtual ~dyna_trees();
  104.  
  105.      void*    inf(d_vertex v) { return v->info; }
  106.        
  107.      d_vertex maketree(void*);
  108.      d_vertex findroot(d_vertex);
  109.      d_vertex findcost(d_vertex, double&);
  110.      void   addcost(d_vertex, double);
  111.      void   link(d_vertex, d_vertex);
  112.      void   cut(d_vertex);
  113. };
  114.  
  115.  
  116. template<class itype>
  117.  
  118. class _CLASSTYPE  tree_collection : public dyna_trees{
  119.  
  120. void copy_inf(GenPtr& x)      { x=Copy(ACCESS(itype,x)); }
  121. void clear_inf(GenPtr& x)     { Clear(ACCESS(itype,x));  }
  122.  
  123. public:
  124.  
  125. d_vertex maketree(itype x)  { return dyna_trees::maketree(Convert(x)); }
  126. itype    inf(d_vertex v)    { return ACCESS(itype,dyna_trees::inf(v)); }
  127.  
  128.  tree_collection() {}
  129. ~tree_collection() {}
  130.  
  131. };
  132.  
  133. #endif
  134.  
  135.